package ljl.alg.jianzhioffer.round2;

import java.util.LinkedList;

/**
 * 这个题我感觉不是很好做
 * 几个序列不太好在脑子里想出来，得列出几个常见情况
 * 而且可能考虑不全，之类的
 * */
public class _31_validate_stack_sequence {
    
    /**
     * 不难，我记着 2022年7月22日15:13:50
     *
     * pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
     * try 1. 尝试使用栈
     * try 2. 感觉，一个指针代替栈
     * try 3. 不行，指针又回去了，还得用栈
     *
     * 居然通过了 2022年7月22日15:33:47，耗时 40 分钟，我日？
     * */
    public boolean validateStackSequences3(int[] pushed, int[] popped) {
        LinkedList<Integer> stack = new LinkedList<>();
        
        int len = pushed.length;
        int pushi = 0, popi = 0;
        while (pushi < len) {
            // 对齐第一个
            while (pushi < len && pushed[pushi] != popped[popi]) {
                stack.push(pushed[pushi++]);
            }
            // 至少得有一个一样的
            if (pushi == len) return false;
            // 找到一个相同的，跳过
            popi++;
            // 相同的弹出
            while (popi < len && !stack.isEmpty() && stack.peek() == popped[popi]) {
                stack.pop();
                popi++;
            }
            // 上面把相同的处理完了，看 push 的下一个数字
            pushi++;
        }
        // popi 在单个字符匹配和栈匹配完成后达到末尾
        return popi == popped.length;
    }
    
    /**
     * 我日
     * 路飞只需要十行
     *
     * 怎么像是个单调栈啥的？
     * */
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        LinkedList<Integer> stack = new LinkedList<>();
        int k = 0;
        for (int i : pushed) {
            stack.push(i);
            while (!stack.isEmpty() && stack.peek() == popped[k]){
                k++;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
}
